Halting Problem

Halting Problem is closely related with reduction.

Church-Turing Thesis

Intuition of Algorithm equals Turing machine that halts on every input.
solve equals decide
decision problem equals language

Object O

\to

"O"

Problem; Given $G$ , is $G$ is a connected graph?
Language: $L = {^{″} G^{″} : G i s a c o n n e c t e d g r a p h}$

Reduction

Abstract

A reduction from A(A over $Σ_{A}$ ) to B(B over $Σ_{B}$ ) is a recursive(computable) function $f (Σ_{A}^{*}) \to Σ_{B}^{*}$ such that for $w \in Σ_{A}^{*}$ , $w \in A$ iff $f (w) \in B$

Theorem: Suppose there is a reduction f from A to B. If B is recursive, that A is recursive.

Proof: $\exists M_{B}$ decides $B$ , find $M_{A}$ to decide $A$ .
$M_{A}$ = on input $w$
(1) compute $f (w)$
(2) run $M_{B}$ on $f (w)$
(3) output the result

Countable

What is Countable

A set is countable if it is finite or it is equinumerous with $N$ .
Let $A$ be a set. The following statements are equiv.
(1) A is countable
(2) $\exists$ injection $f : A \to N$
(3) there exists some way to enumerate $A$ such that for $a \in A$ , $a$ can be enumerated within n steps where n only depends on $a$

Lemma: Any subset of a countable set is countable

Lemma: Turing Machine is countable.

Let

Σ

be an alphabet.

Σ^{*}

is countable

enumerate all the strings in $Σ^{*}$ , in increasing length $\forall w \in Σ^{*}$ , $w$ will be listed within

| Σ^{0} | + | Σ^{1} | + \dots | Σ^{| w |} | s t e p s

L

is uncountable

Let $Σ$ be some alphabet
Let $L$ be the set of all languages
Suppose that $L$ is countable
The language in $L$ can be listed as

L_{1}, L_{2}, L_{3}, \dots

Since $Σ^{*}$ is countable, the strings in $Σ^{*}$ can be listed as $$S_1, S_2, S_3, \dots$$
$D = {s_{i} : s_{i} \notin L_{i}}$ is a language over $Σ$

\begin{aligned} f o r a n y i, s_{i} \in D \\ i f a n d o n l y i f s_{i} \notin L_{i} \\ \Rightarrow D \notin L_{i} \\ \Rightarrow D \notin L \end{aligned}

Definition

Give the definition of $H$ and $H_{d}$

H = {^{″} M^{″}^{″} w^{″} : M i s a T M t h a t h a l t s o n w}

H_{d} = {^{″} M^{″} : M i s a T M t h a t d o e s N O T h a l t o n^{″} M^{″}}

$H$ is recursively enumerable but not recursive.
$H_{d}$ is not recurisively enumerable.
If there is a reduction from $H$ to $A$ , $A$ is not recursive

Examples

$A$ = {" $M$ ": $M$ is a TM that halts on empty input} is not recursive
$B$ = {" $M$ ": $M$ is a TM that halts on some input} is not recursive
$C$ = {" $M$ ": $M$ is a TM that halts on every input} is not recursive
$D$ = {" $M_{1}$ "" $M_{2}$ ": $M_{1}$ and $M_{2}$ are two TMs with $L (M_{1}) = L (M_{2})$ } is not recursive
$R_{T M}$ = {" $M$ ": $M$ is a TM with $L (M)$ is regular} is not recursive
$C F_{T M}$ = {" $M$ ": $M$ is a TM with $L (M)$ is context-free} is not recursive
$R E C_{T M}$ = {" $M$ ": $M$ is a TM with $L (M)$ is recursive} is not recursive

A

= {"

M

M

is a TM that halts on empty input} is not recursive 以及

B

和

C

的证明

构造 Deduction f("M""w") = on input u, run M on w.

那么有两种情况：

第一种情况，M 不停机，那么 f("M""w") 也不停机，就不被 A 接受；
第二种情况，M 停机，那么 f("M""w") 也停机，无论此时的 input u 是什么，都是被接受的，显然 empty input 也被包含在内，同理可推至 B 和 C 的情况。

Proof:

D

= {"

M_{1}

M_{2}

M_{1}

and

M_{2}

are two TMs with

L (M_{1}) = L (M_{2})

} is not recursive

思路： $C \leq D$
构造 f("M") = "M" "M*"，同时 M* 满足对于所有的输入都停机，比如 on input u, halt

对 $M$ 进行分类讨论：

$^{″} M^{″} \in C$ ，M halts on every input， $L (M) = L (M *)$
$^{″} M^{″} \notin C$ ，M does not halt on every input， $L (M) \neq L (M *)$

$∴$ $L (M) = L (M^{*})$ , $f (^{″} M^{″}) \in D$

Rice's theorem

Rice's theorem
$R$ = {"M": $M$ is a TM with $L (M) \in L$ } is not recursive where $L$ is a proper, non-empty subset of all recursively enumerable language.

Proof: Make a reduction from $H$ to $R$
(1) If $\emptyset \notin L$
construct f("M""w") = on input $v$
step1 run $M$ on $w$
step2 run $M_{A}$ on $v$ , where $M_{A}$ satisfy that $L (M_{A}) \in L$

L [f (^{″} M^{″}^{″} w^{″})] = {\begin{cases} L (M_{A}) = A \in L & i f^{″} M^{″}^{″} w^{″} \in H \\ \emptyset \notin L & i f^{″} M^{″}^{″} w^{″} \notin H \end{cases}

$∴^{″} M^{″}^{″} w^{″} \in H$ if and only if $f (^{″} M^{″}^{″} w^{″}) \in R$
(2) If $\emptyset \in L$
transform the the problem from $L$ into $\bar{L}$

Closure Property

operator	recursive	recursive enumerable
$\cup$	√	√
$\cap$	√	√
$\overset{―}{}$	√	×
$\circ$	√	√
$⋆$	√	√

M_{A \cup B}

= on input w

run $M_{A}$ and $M_{B}$ in parallel on w
if at least one of them halt
halt

M_{A \circ B}

= on input w

non-deterministically divide w=uv
run $M_{A}$ on $u$ and run $M_{B}$ on $v$
if $M_{A}$ and $M_{B}$ both halt
halt

Lemma: A language

A

is recursive if and only if

A

and

\bar{A}

are recursively enumerable

H

is recursively enumerable,

\bar{H}

is not recursively enumerable

According to the Lemma, because $H$ is not enumerable

Turing Enumerable

Definition

We say a TM $M$ enumerates a language $L$ is for some state $q$ ,

L = {w : (s, ▹ \underset{―}{⊔}) ⊢_{M}^{*} (q, ▹ \underset{―}{⊔} w)}

Theorem: A language L is Turing enumerable iff it is recurisve enumerate

⇒
for $M$ enumerate $L$
construct $M^{'}$ semi-decide $L$
$M^{'}$ = on input $w$

run $M$ to enumerate $L$
Every time $M$ outputs a string
compare it with input $w$
halt if they match

⇐
for $M$ semi-decide $L$
construct $M^{'}$ enumerate $L$
$M^{'}$ =

for $i = 1, 2, 3, . . .$
- for $s = s_{0}, s_{1}, . . . s_{i}$
  - run $M$ on $s$ for $i$ steps
  - if $M$ halts on $s$ within $i$ steps
    - output $s$

Lexicographically Turing Enumerable

Definition

Let $M$ be a TM that enumerates $L$
We say M lexicographically enumerate $L$ if whenever

(q, ▹ \underset{―}{⊔} w) ⊢_{M}^{+} (q, ▹ \underset{―}{⊔} w^{'})

$w^{'}$ is after $w$ in lexicographically order, $⊢_{M}^{+}$ means at least one step.

What is lexicographical?

Theorem: A language L is lexicographically Turing enumerable iff it is recursive

⇐
$\exists$ $M$ decide $L$
construct $M^{'}$ lexico. enum. $L$
M' =

enumerate all strings over in lexico. order
every a tring s is enumerated
- run $M$ on $s$
- If $M$ accepts $s$
- output s

⇒
$\exists$ $M$ lexico. enum. $L$
construct $M^{'}$ decide $L$
$M^{'}$ = on input $w$

run $M$ to enumerate all string in $L$ until $M$ output a string that is after $w$ in lexico. order.
If $w$ is among the ouput string.
- accept
else
- reject

Grammar

Definition: A grammar is 4-tuple $G = (V, Σ, S, R)$
- $V$ is an alphabet
- $Σ \subseteq V$ : the set of terminals
- $S \in V - Σ$ : start symbol
- $R$ : a finite subset of $(V^{*} (V - Σ) V^{*}) \times V^{*}$
compared with Context Free Grammar, the Grammar is unrestricted grammar.

Constrcut grammar generates {

a^{n} b^{n} c^{n} : n \geq 1

}

$S \to S A B C$
$B A \to A B, C A \to A C, C B \to B C$
$S \to T_{c}, C T_{c} \to T_{c} c, B T_{c} \to B T_{b}$
$B T_{b} \to T_{b} b, A T_{b} \to A T_{a}$
$A T_{a} \to T_{a} a, T_{a} \to e$

Theorem: A language is generated by a grammar iff it is semi-decided by a TM

⇒ Given $G = (v, Σ, S, R)$ , Constrcut $M = (K, Σ, δ, s, H)$

M = on input $w$

layer 0 =
for i = 1, 2, 3, ...
- construct layer i from layer i-1
- if $w$ in layer i
  - halt

⇐ Given $M = (K, Σ, δ, s, H)$ , construct $G$ to generate $L (M)$
assume: (1) $K \cup Σ = \emptyset$ (2) $H = {h}$ (3) if $M$ halts, it is always in configuration $(h, Δ \underset{―}{⊔})$
后面证明就省略了...

$A_{G}$ = {"G""w": $G$ is a grammar that generates $w$ } is not recursive